Minimum-Cost Heterogeneous Node Placement in Wireless Sensor Networks

Abstract

The operational cost-effectiveness of wireless sensor networks depends on the placement of heterogeneous nodes: base stations, sensor nodes, and relay nodes. To achieve the global optimality of minimum-cost heterogeneous node placement, we find the locations of base stations, sensor nodes, and relay nodes, simultaneously. The objective is to minimize the sum of node production and placement costs and transmission outage probabilities in the routing tree. First, we formulate this minimum-cost heterogeneous node placement problem as a new NP-hard Steiner tree problem. Then, to solve this problem for both small and large instances, we propose an exponential-Time exact algorithm, a polynomial-Ti..